import java.util.ArrayList;
import java.util.HashSet;
import java.util.Random;



public class IterativeDeepeningDepthLimitedMinimaxWithAlphaBetaPruningSearchEngine implements SearchEngine {

	private static final int DEPTH_LIMIT = 50;
	
	private Node root;
	// if there is more than one move with the same heuristic value, randomize between them
	private HashSet<MovePerformer> movesBucket;
	
	public IterativeDeepeningDepthLimitedMinimaxWithAlphaBetaPruningSearchEngine(Board board) {
		root = new Node();
		root.setBoard(board);
		int player = Node.MAX_PLAYER;
		if(board.getPlayerPieces().get(0).getColor() == Piece.COLOR_BLACK) player = Node.MIN_PLAYER;
		root.setPlayer(player);
		root.setLevel(0);
		
		movesBucket = new HashSet<MovePerformer>();
	}
	
	@Override
	public void execute(Move[] moves, Piece[] pieces, int playerColor) {
		root.getBoard().setMovesArray(moves);
		
		root.expand();
		
		int depth = 1;
		while(true){
			double alpha = Double.NEGATIVE_INFINITY;
			double beta = Double.POSITIVE_INFINITY;
			
			if(root.getPlayer() == Node.MIN_PLAYER){
				alpha = Double.POSITIVE_INFINITY;
				beta = Double.NEGATIVE_INFINITY;
			}
			
			minimaxEval(root, depth, alpha, beta);
			MovePerformer bestMove = getBestMove();
			if(bestMove == null){
				System.out.println("Could not find a move with depth " + depth);
				if(depth == DEPTH_LIMIT) break;
				depth++;
			}else{
				System.out.print("Found a move with depth " + depth + " -> ");
				movesBucket.clear();
				bestMove.performMove();
				break;
			}
		}
		
	}
	
	public double minimaxEval(Node node, int depthLeft, double alpha, double beta){
		// Return utility if game over or depth limit reached
		if (node.isGoal() || depthLeft == 0){
			return node.utility();
		}
		
		// Otherwise, generate children
		ArrayList<Node> children = node.expand();
		
		if(node.getPlayer() == Node.MAX_PLAYER){
			for (Node child : children) {
				double minimaxForChild = minimaxEval(child, depthLeft-1, alpha, beta);
				if(alpha > minimaxForChild){
					if(movesBucket.isEmpty() || alpha == child.utility()){
						movesBucket.add(child.getUsedMove());
					}
				}else{
					alpha = minimaxForChild;
					movesBucket.clear();
				}
				if(beta <= alpha){
					// beta pruning:
					// Search will stop below MAX nodes with alphas greater or equal to the beta of any MIN ancestor
					break;
				}
			}
			return alpha;
		}else{
			for (Node child : children) {
				double minimaxForChild = minimaxEval(child, depthLeft-1, alpha, beta);
				if(beta < minimaxForChild){
					if(movesBucket.isEmpty() || beta == child.utility()){
						movesBucket.add(child.getUsedMove());
					}
				}else{					
					beta = minimaxForChild;
					movesBucket.clear();
				}
				if(beta <= alpha){
					// alpha pruning:
					// Search will stop below MIN nodes with betas less or equal to the alpha of any MAX ancestor
					break;
				}
			}
			return beta;
		}
	}
	
	public MovePerformer getBestMove() {
		if(!movesBucket.isEmpty()){
			int randomIndex = new Random().nextInt(movesBucket.size());
			int i = 0;
			for(MovePerformer performer : movesBucket) {
			    if (i == randomIndex) return performer;
			    else i = i + 1;
			}
		}

		return null;
	}

}
